package Offer;

/**
 * @author 是阿秋啊
 * @date 2022/04/14 20:38
 **/
public class Num36BigPeople {
    NodeRoot head,pre;
    public NodeRoot treeToDoublyList(NodeRoot root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        pre.right = head;
        head.left = pre;
        return head;
    }

    private void dfs(NodeRoot root) {
        if (root == null) {
            return;
        }
        // 定义当前节点
        NodeRoot cur = root;
        // 先走到最左子节点
        dfs(root.left);
        // pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur
        if (pre != null) {
            // pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
            pre.right = cur;
        }else {
            // 当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
            head = cur;
        }
        // 连接pre与cur，且移动pre指向cur
        cur.left = pre;
        pre = cur;
        // 走到最右子节点，作为尾节点
        dfs(root.right);
    }
}
